{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #子结构判断"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isSubStructure"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子结构判断"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定两棵二叉树 <code>tree1</code> 和 <code>tree2</code>，判断 <code>tree2</code> 是否以 <code>tree1</code> 的某个节点为根的子树具有 <strong>相同的结构和节点值</strong> 。<br />\n",
    "注意，<strong>空树&nbsp;</strong>不会是以 <code>tree1</code> 的某个节点为根的子树具有 <strong>相同的结构和节点值</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694684670-vwyIgY-two_tree.png\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree1 = [1,7,5], tree2 = [6,1]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>tree2 与 tree1 的一个子树没有相同的结构和节点值。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://pic.leetcode.cn/1694685602-myWXCv-two_tree_2.png\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>tree1 = [3,6,7,1,8], tree2 = [6,1]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>tree2 与 tree1 的一个子树拥有相同的结构和节点值。即 6 - &gt; 1。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<p><code>0 &lt;= 节点个数 &lt;= 10000</code></p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shu-de-zi-jie-gou-lcof](https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shu-de-zi-jie-gou-lcof](https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4]\\n[3]', '[-1,3,2,0]\\n[]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        self.rootA = []\n",
    "        if B == None:\n",
    "            return False\n",
    "        def dfs(A):\n",
    "            if A == None:\n",
    "                return\n",
    "            if A.val == B.val:\n",
    "                self.rootA.append(A)\n",
    "            dfs(A.left)\n",
    "            dfs(A.right)\n",
    "            return\n",
    "        dfs(A)\n",
    "        if self.rootA == None:\n",
    "            return False\n",
    "        def match(A, B):\n",
    "            if A == None and B == None:\n",
    "                return\n",
    "            if (A == None and B != None):\n",
    "                self.ans = False\n",
    "                return\n",
    "            if (A != None and B == None):\n",
    "                return\n",
    "            if A.val != B.val:\n",
    "                self.ans = False\n",
    "                return\n",
    "            match(A.left, B.left)\n",
    "            match(A.right, B.right)\n",
    "        for root in self.rootA:\n",
    "            self.ans = True\n",
    "            match(root, B)\n",
    "            if self.ans:\n",
    "                return self.ans\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not B:\n",
    "            return False\n",
    "        stack_A = [A] if A else []\n",
    "        while stack_A:\n",
    "            cur_A = stack_A.pop()\n",
    "            if self._isContain(cur_A, B):\n",
    "                return True\n",
    "            if cur_A.left:\n",
    "                stack_A.append(cur_A.left)\n",
    "            if cur_A.right:\n",
    "                stack_A.append(cur_A.right)\n",
    "        return False\n",
    "\n",
    "    @functools.lru_cache()\n",
    "    def _isContain(self, A: TreeNode, B: TreeNode):\n",
    "        if not B:\n",
    "            return True\n",
    "        if (B and not A) or A.val != B.val:\n",
    "            return False\n",
    "        return self._isContain(A.left, B.left) and self._isContain(A.right, B.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        print(str(A))\n",
    "        print(str(B))\n",
    "        if B is None:\n",
    "            return False\n",
    "        nodes = self.inder_tree(A)\n",
    "        for node in nodes:\n",
    "            if node and node.val == B.val:\n",
    "                if self.check(node, B):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def inder_tree(self, node):\n",
    "        if node is None:\n",
    "            return []\n",
    "        return [node] + self.inder_tree(node.left) + self.inder_tree(node.right)\n",
    "            \n",
    "    \n",
    "    def check(self, node1, node2):\n",
    "        if node2 is None:\n",
    "            return True\n",
    "        if node1 is None:\n",
    "            return False\n",
    "        if node1.val == node2.val:\n",
    "            return self.check(node1.left, node2.left) and self.check(node1.right, node2.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def isequal(root1,root2):\n",
    "            if not root2:\n",
    "                return True\n",
    "            elif not root1 :\n",
    "                return False\n",
    "            if root1.val!=root2.val:\n",
    "                return False\n",
    "            if not isequal(root1.left,root2.left):\n",
    "                return False\n",
    "            if not isequal(root1.right,root2.right):\n",
    "                return False\n",
    "            return True\n",
    "        \n",
    "        a=isequal(A,B)\n",
    "        print(a)\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        if a:\n",
    "            return True\n",
    "        b=self.isSubStructure(A.left,B)\n",
    "        if b:\n",
    "            return True\n",
    "        if A and B:\n",
    "            c=self.isSubStructure(A.right,B)\n",
    "            if c:\n",
    "                return True\n",
    "        return a or b or c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recur(self,A, B):\n",
    "        if not B: return True\n",
    "        if not A or A.val != B.val: return False\n",
    "        return self.recur(A.left, B.left) and self.recur(A.right, B.right)\n",
    "\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        \n",
    "        return bool(A and B) and (self.recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "class TreeNode:\n",
    "    def __init__(self, x):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not A or not B: return False\n",
    "        return self.a_has_b(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "    \n",
    "\n",
    "    def a_has_b(self, a: TreeNode, b: TreeNode) -> bool:\n",
    "        if not b: return True\n",
    "        if not a or not a.val == b.val: return False\n",
    "        return self.a_has_b(a.left, b.left) and self.a_has_b(a.right, b.right)\n",
    "        \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def check(a, b):\n",
    "            if not b: return True\n",
    "            if not a or a.val!=b.val: return False\n",
    "            return check(a.left, b.left) and check(a.right, b.right)\n",
    "        \n",
    "        if not A or not B: return False\n",
    "        return check(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recur(self,A,B):\n",
    "        if not B:return True\n",
    "        if not A or (A.val!=B.val):return False\n",
    "        return self.recur(A.left,B.left) and self.recur(A.right,B.right)\n",
    "\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not A or not B:return False\n",
    "        # if A.val!=B.val:return False\n",
    "        return self.recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:        \n",
    "        def recur(A,B):\n",
    "            if not B:return True\n",
    "            if not A or A.val!=B.val:return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        \n",
    "        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not A: return False\n",
    "        Q = collections.deque()\n",
    "        def dfs(T: TreeNode):\n",
    "            if T and B and T.val == B.val:\n",
    "                Q.append(T)\n",
    "            if T.left: dfs(T.left)\n",
    "            if T.right: dfs(T.right)\n",
    "        dfs(A)\n",
    "        def compare(T1: TreeNode, T2: TreeNode) -> bool:\n",
    "            if not T1 or not T2 or T1.val != T2.val: return False\n",
    "            if not T2.right and T2.left: return compare(T1.left, T2.left)\n",
    "            if not T2.left and T2.right: return compare(T1.right, T2.right)\n",
    "            if T2.left and T2.right: return compare(T1.left, T2.left) and compare(T1.right, T2.right)\n",
    "            return True\n",
    "        while Q:\n",
    "            T =  Q.popleft()\n",
    "            if compare(T, B): return compare(T, B)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def recur(self, A, B):\n",
    "        if not B:\n",
    "            return True\n",
    "        if not A:\n",
    "            return False\n",
    "        return A.val == B.val and self.recur(A.left, B.left) and self.recur(A.right, B.right)\n",
    "\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        \n",
    "        if not A or not B:\n",
    "            return False\n",
    "        \n",
    "        return (self.recur(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        def check(head1, head2):\n",
    "            if head1 and not head2:\n",
    "                return True\n",
    "\n",
    "            if not head1 and head2:\n",
    "                return False\n",
    "\n",
    "            if not head1 and not head2:\n",
    "                return True\n",
    "\n",
    "            if head1.val==head2.val:\n",
    "                return check(head1.left, head2.left) and check(head1.right, head2.right)\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        if not B:\n",
    "            return False\n",
    "\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if check(node, B):\n",
    "                    self.ans = True\n",
    "                    return \n",
    "                else:\n",
    "                    dfs(node.left)\n",
    "                    dfs(node.right)\n",
    "\n",
    "        self.ans = False\n",
    "        dfs(A)\n",
    "\n",
    "        return self.ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def isSameTree(node1, node2):\n",
    "            # 节点2（B） 为空时，递归结束， 返回true\n",
    "            if not node2: return True\n",
    "            # 节点1（A） 为空时，递归结束， 返回False\n",
    "            if not node1 or node1.val !=node2.val: return False\n",
    "            return isSameTree(node1.left, node2.left) and isSameTree(node1.right, node2.right)\n",
    "        if not A or not B: return False\n",
    "        return isSameTree(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            # 这里的B为空，说明所有B的node都匹配完成；\n",
    "            if not B: \n",
    "                return True\n",
    "            if not A or A.val != B.val: \n",
    "                return False\n",
    "            sub_left =  recur(A.left, B.left)\n",
    "            sub_right = recur(A.right, B.right)\n",
    "            return sub_left and sub_right\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self,nodeA,nodeB):\n",
    "        if not nodeB:\n",
    "            return True\n",
    "        if not nodeA:\n",
    "            return False\n",
    "        return nodeA.val == nodeB.val and self.dfs(nodeA.left,nodeB.left) and self.dfs(nodeA.right,nodeB.right)\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not A or not B:return False\n",
    "        return self.dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "       def recur(A,B):\n",
    "           if not B:\n",
    "               return True\n",
    "           elif not A or A.val != B.val:\n",
    "                return False\n",
    "           return recur(A.left,B.left) and recur (A.right,B.right)\n",
    "       return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        \n",
    "        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        \n",
    "        def recur(A,B):\n",
    "            if not B: return True\n",
    "            if not A or A.val!=B.val: return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        \n",
    "            \n",
    "        if not (A and B):\n",
    "            return False\n",
    "        elif not recur(A,B):\n",
    "            return self.isSubStructure(A.right,B) or self.isSubStructure(A.left,B)\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def issub(a,b):\n",
    "            if not b: return True\n",
    "            elif not a or a.val != b.val: return False\n",
    "            else: return issub(a.left,b.left) and issub(a.right,b.right)\n",
    "        return bool(A and B) and (issub(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B: return True\n",
    "            elif not A or A.val!=B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        if not A or not B: return False\n",
    "        return recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubNode(self, treeA, treeB):\n",
    "        # 逐Node检查一致性\n",
    "        if not treeB:\n",
    "            return True\n",
    "        if not treeA or treeA.val != treeB.val:\n",
    "            return False\n",
    "\n",
    "        return self.isSubNode(treeA.left, treeB.left) and self.isSubNode(treeA.right, treeB.right)\n",
    "\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        # 主函数检查 自己 与 B 的一致性\n",
    "        # 如果不行，检查自己的左/右节点与B的一致性\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        \n",
    "\n",
    "        return  self.isSubNode(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "         \n",
    "    \n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def check(a, b):\n",
    "            if not b: return True\n",
    "            if a and a.val == b.val and check(a.left, b.left) and check(a.right, b.right):\n",
    "                return True\n",
    "            else: return False\n",
    "        if not B: return False\n",
    "        if not A: return False\n",
    "        lst = [A]\n",
    "        while lst:\n",
    "            node = lst.pop()\n",
    "            if node.val == B.val and check(node, B):\n",
    "                return True\n",
    "            if node.left: lst.append(node.left)\n",
    "            if node.right: lst.append(node.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def compare(self,A,B):\n",
    "        if not B: return True\n",
    "        if not A: return False\n",
    "        if A.val!=B.val: return False\n",
    "        return self.compare(A.left,B.left) and self.compare(A.right,B.right)\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not B: return False\n",
    "        if not A: return False\n",
    "        return self.compare(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B:return True\n",
    "            if not A or A.val != B.val:return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.flag = False\n",
    "    def find_same_tree(self, A, B):\n",
    "        if A is None and B is None:\n",
    "            return True\n",
    "        elif B is None:\n",
    "            return True\n",
    "        elif A is None:\n",
    "            return False\n",
    "        return A.val == B.val and self.find_same_tree(A.left,B.left) and self.find_same_tree(A.right,B.right)\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if A is None or B is None:\n",
    "            return self.flag\n",
    "        # print(A.val)\n",
    "        if A.val == B.val:\n",
    "            # print(A.val)\n",
    "            if self.find_same_tree(A,B):\n",
    "                self.flag = True\n",
    "            # return self.flag\n",
    "        # else:\n",
    "        self.isSubStructure(A.left, B)\n",
    "        self.isSubStructure(A.right, B)\n",
    "        return self.flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def fun(A, B):\n",
    "            if not B:\n",
    "                return True \n",
    "            if not A or A.val != B.val:\n",
    "                return False \n",
    "            return fun(A.left, B.left) and fun(A.right, B.right)\n",
    "        return bool(A and B) and (fun(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def isTrue(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val!=B.val:\n",
    "                return False\n",
    "            else:\n",
    "                return isTrue(A.left,B.left) and isTrue(A.right,B.right)\n",
    "        return bool(A and B) and (isTrue(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        \"\"\"\n",
    "        判断两颗二叉树是否相同\n",
    "        \"\"\"\n",
    "        def is_same_tree(t1,t2):\n",
    "            # if t1 is None and t2 is None:\n",
    "            if t2 is None:\n",
    "\n",
    "                return True\n",
    "            elif t1 is None or t2 is None:\n",
    "            # elif t1 is None:\n",
    "                return False\n",
    "            elif t1.val != t2.val:\n",
    "                return False\n",
    "            else:\n",
    "                return is_same_tree(t1.left,t2.left) and is_same_tree(t1.right, t2.right)\n",
    "        if A is None or not B:\n",
    "            return False\n",
    "        # if is_same_tree(A,B):\n",
    "        #     return True\n",
    "\n",
    "        return is_same_tree(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def helper(root1,root2):\n",
    "            if root2 is None:\n",
    "                return True\n",
    "            if root1 is None:\n",
    "                return False\n",
    "            if root1.val == root2.val:\n",
    "                return helper(root1.left,root2.left) and helper(root1.right,root2.right)\n",
    "            return False\n",
    "\n",
    "        if A is None or B is None:\n",
    "            return False\n",
    "        if A.val == B.val:\n",
    "            if helper(A,B):\n",
    "                return True\n",
    "        return self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B:return True\n",
    "            if not A or A.val!=B.val:return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "\n",
    "        if not A or not B:return False\n",
    "        return recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        ## 以节点a为根节点子树，是b的子结构\n",
    "        def recon(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val :return False\n",
    "            return recon(A.left, B.left) and recon(A.right, B.right)\n",
    "\n",
    "\n",
    "        # 采用先序遍历\n",
    "        if A == None or B==None:\n",
    "            return False\n",
    "\n",
    "        return  recon(A, B) or  self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # 572. 另一棵树的子树 https://leetcode.cn/problems/subtree-of-another-tree/submissions/\n",
    "    # 本题是子结构, 572题是子树\n",
    "    # 子树需要A和B全部遍历完, 需要A和B完全相同\n",
    "    # 而子结构只需要B遍历完, A可以没有遍历完, 就认为B是A的子结构,\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        # 双重dfs\n",
    "        def is_sub(A, B): # 返回B是不是A的子结构, 572题该函数的返回值的意义是 A和B是否完全相同\n",
    "            if not B: return True  # 与572题不同之处, B遍历完了, A可以没有遍历完, 就认为B是A的子结构, \n",
    "            if not A or A.val != B.val: return False\n",
    "            return is_sub(A.left, B.left) and is_sub(A.right, B.right)\n",
    "        if not A or not B: return False\n",
    "        return is_sub(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def dfs(a, b):\n",
    "            if not b:\n",
    "                return True\n",
    "            if not a or a.val != b.val:\n",
    "                return False\n",
    "            return dfs(a.left, b.left) and dfs(a.right, b.right)\n",
    "        \n",
    "        return bool(A and B) and (dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def fun(A, B):\n",
    "            if not B:\n",
    "                return True\n",
    "\n",
    "            if not A or A.val != B.val:\n",
    "                return False \n",
    "            return fun(A.left, B.left) and fun(A.right, B.right)\n",
    "        return bool(A and B) and (fun(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def dfs(node1, node2):\n",
    "            if  node2 is None:\n",
    "                return True\n",
    "            if node1 is None:\n",
    "                return False\n",
    "            if node1.val == node2.val:\n",
    "                return dfs(node1.left, node2.left) and dfs(node1.right, node2.right)\n",
    "            else:\n",
    "                return False\n",
    "        \n",
    "        def dfss(node1, node2):\n",
    "            if node1 is None:\n",
    "                return False\n",
    "            return dfs(node1, node2) or dfss(node1.left, node2) or dfss(node1.right, node2)\n",
    "                \n",
    "        if B is None:\n",
    "            return False\n",
    "\n",
    "        return dfss(A, B)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A:\n",
    "                return False\n",
    "            return True  if  A.val==B.val and recur(A.left,B.left) and recur(A.right,B.right) else False\n",
    "        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B:return True\n",
    "            if not A or A.val!=B.val:return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        if not B or not A:return False\n",
    "        return recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def isSub(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            elif not A:\n",
    "                return False\n",
    "            elif A.val != B.val:\n",
    "                return False\n",
    "            else:\n",
    "                return isSub(A.left,B.left) and isSub(A.right,B.right)\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        return isSub(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        # 以当前结点A为根结点的子树是否包含树B\n",
    "        def recur(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val !=B.val:\n",
    "                return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        return recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B:return True\n",
    "            if not A or A.val != B.val:return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A, B):\n",
    "        def recur(A, B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "        \n",
    "        if not A or not B:\n",
    "            return False\n",
    "        return recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: \n",
    "        # if not ):\n",
    "        #     return False\n",
    "        # def dfs(A,B):\n",
    "        #     if not A:\n",
    "        #         return False\n",
    "        #     if not B:\n",
    "        #         return True\n",
    "        #     if A.val != B.val :\n",
    "        #         return False\n",
    "        #     return  dfs(A.left,B.left) and dfs(A.right,B.right)\n",
    "        # if bool(A and B) and (dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)):\n",
    "        #     return True\n",
    "        # return False \n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        def cur(A, B):\n",
    "            if not B: return True   \n",
    "            if not A or A.val!=B.val: return False\n",
    "\n",
    "            return cur(A.left,B.left) and cur(A.right,B.right)\n",
    "        \n",
    "        return bool(A and B) and (cur(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B:return True\n",
    "            if not A or A.val != B.val:return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        return bool(A and B) and (recur(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "def node_same(node1: TreeNode, node2: TreeNode):\n",
    "    if node1 is None and node2 is None:\n",
    "        return True\n",
    "    if node1 is None and node2 is not None:\n",
    "        return False\n",
    "    if node1 is not None and node2 is None:\n",
    "        return False\n",
    "    return node1.val == node2.val\n",
    "\n",
    "\n",
    "def determine(node: TreeNode, target: TreeNode):\n",
    "    if node_same(node, target):\n",
    "        node_left = node.left\n",
    "        target_left = target.left\n",
    "\n",
    "        if target_left is not None:\n",
    "            left_result = determine(node_left,target_left)\n",
    "        else:\n",
    "            left_result = True\n",
    "\n",
    "        node_right = node.right\n",
    "        target_right = target.right\n",
    "\n",
    "        if target_right is not None:\n",
    "            right_result = determine(node_right, target_right)\n",
    "        else:\n",
    "            right_result = True\n",
    "        return left_result and right_result\n",
    "    return False\n",
    "\n",
    "\n",
    "def search_head(node: TreeNode, target: TreeNode):\n",
    "    if node is None:\n",
    "        return False\n",
    "    if node.val == target.val:\n",
    "        result = determine(node, target)\n",
    "        if result:\n",
    "            return True\n",
    "        else:\n",
    "            left = search_head(node.left, target)\n",
    "            right = search_head(node.right, target)\n",
    "            return left or right\n",
    "\n",
    "    else:\n",
    "        left = search_head(node.left, target)\n",
    "        right = search_head(node.right, target)\n",
    "        return left or right\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if B is None:\n",
    "            return False\n",
    "        return search_head(A, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        def is_subTree(A, B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A:\n",
    "                return False\n",
    "            if A.val != B.val:\n",
    "                return False\n",
    "            return is_subTree(A.left, B.left) and is_subTree(A.right, B.right)\n",
    "\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        if is_subTree(A, B):\n",
    "            return True\n",
    "        return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        target_tree = B\n",
    "        wether_can = False\n",
    "        list_quene = [A]\n",
    "\n",
    "        def dps(node_se, target_node):\n",
    "            nonlocal wether_can\n",
    "            if not wether_can:\n",
    "                return\n",
    "            if target_node is None:\n",
    "                return\n",
    "            elif node_se is not None and target_node is not None:\n",
    "                if node_se.val == target_node.val:\n",
    "                    dps(node_se.left, target_node.left)\n",
    "                    dps(node_se.right, target_node.right)\n",
    "                else:\n",
    "                    wether_can = False\n",
    "                    return\n",
    "            else:\n",
    "                wether_can = False\n",
    "\n",
    "\n",
    "        def bps(list_quene, target_tree):\n",
    "            nonlocal wether_can\n",
    "            # now_list_quene = list_quene.copy()\n",
    "            for tree in list_quene:\n",
    "                if wether_can:\n",
    "                    return\n",
    "                # if tree is not None:\n",
    "                if tree.val == target_tree.val:\n",
    "                    wether_can = True\n",
    "                    dps(tree, target_tree)\n",
    "                if tree.left is not None:\n",
    "                    list_quene.append(tree.left)\n",
    "                if tree.right is not None:\n",
    "                    list_quene.append(tree.right)\n",
    "                # list_quene.pop(0)\n",
    "\n",
    "        if target_tree is not None:\n",
    "            # while len(list_quene) != 0 and not wether_can:\n",
    "            bps(list_quene, target_tree)\n",
    "\n",
    "        return wether_can\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not B or not A:\n",
    "            return False\n",
    "        status = False\n",
    "\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            nonlocal status\n",
    "            if node.val == B.val:\n",
    "                status = check(node, B)\n",
    "            if node.left:\n",
    "                dfs(node.left)\n",
    "            if node.right:\n",
    "                dfs(node.right)\n",
    "\n",
    "        def check(nA, nB):\n",
    "            if not nB: return True\n",
    "            if not nA: return False\n",
    "            if nA.val != nB.val: return False\n",
    "\n",
    "            return check(nA.left, nB.left) and check(nA.right, nB.right)\n",
    "\n",
    "        dfs(A)\n",
    "\n",
    "        return status"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        \n",
    "        def assist(a,b):\n",
    "            nonlocal B\n",
    "            if not a and b:\n",
    "                return False\n",
    "            if not b and a:\n",
    "                return True\n",
    "            if not a and not b:\n",
    "                return True\n",
    "            \n",
    "            if a.val==b.val:\n",
    "                if assist(a.left,b.left) and assist(a.right,b.right):\n",
    "                    return True\n",
    "            if b!=B:\n",
    "                return False\n",
    "            return assist(a.left,b) or assist(a.right,b)\n",
    "        \n",
    "        return assist(A,B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def dfs(a, b):\n",
    "            if not b:\n",
    "                return True\n",
    "            if not a or a.val != b.val:\n",
    "                return False\n",
    "            return dfs(a.left, b.left) and dfs(a.right, b.right)\n",
    "        return bool(A and B) and (dfs(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B) )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        def is_same(node1, node2):\n",
    "            if not node2:\n",
    "                return True\n",
    "            if not node1 or node1.val != node2.val:\n",
    "                return False\n",
    "            return is_same(node1.left, node2.left) and is_same(node1.right, node2.right)\n",
    "\n",
    "        return bool(A and B) and (is_same(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: \n",
    "                return True\n",
    "            if not A or A.val != B.val: \n",
    "                return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        def recur(A, B):\n",
    "\n",
    "            if not B: return True\n",
    "\n",
    "            if not A or A.val != B.val: return False\n",
    "\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B) :\n",
    "                if not B :return True\n",
    "                if not A or A.val != B.val :return False\n",
    "                return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        \n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool: \n",
    "        if not A or not B:\n",
    "            return False\n",
    "        def dfs(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A:\n",
    "                return False\n",
    "            \n",
    "            if A.val != B.val :\n",
    "                return False\n",
    "            return  dfs(A.left,B.left) and dfs(A.right,B.right)\n",
    "        if dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B):\n",
    "            return True\n",
    "        return False \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "        return bool(A and B)  and (self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B) or recur(A, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "        \n",
    "        if not A or not B:\n",
    "            return False\n",
    "        return (recur(A,B) or self.isSubStructure(A.left,B)) or (recur(A,B) or self.isSubStructure(A.right,B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "\n",
    "        if not B:\n",
    "            return False\n",
    "        if not A:\n",
    "            return False\n",
    "\n",
    "        def sameTree(A, B):\n",
    "            if not B and not A:\n",
    "                return True\n",
    "\n",
    "            if (A and not B) or (B and not A):\n",
    "                return False\n",
    "\n",
    "            if A.val != B.val:\n",
    "                return False\n",
    "            \n",
    "            res = True\n",
    "            if B.left:\n",
    "                res = res and sameTree(A.left, B.left)\n",
    "            if B.right:\n",
    "                res = res and sameTree(A.right, B.right)\n",
    "            return  res\n",
    "\n",
    "        if sameTree(A, B):\n",
    "            return True\n",
    "\n",
    "        return self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def compare(a,b):\n",
    "            if b:\n",
    "                if not a:\n",
    "                    return False\n",
    "                else:\n",
    "                    return (a.val==b.val) and compare(a.left,b.left) and compare(a.right,b.right)\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        def search(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if node.val == B.val:\n",
    "                #开始比对\n",
    "                if compare(node,B) is True:\n",
    "                    return True\n",
    "                else:\n",
    "                    return search(node.left) or search(node.right)\n",
    "            else:\n",
    "                return search(node.left) or search(node.right)\n",
    "        if not B:\n",
    "            return False\n",
    "        return search(A)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B:return True\n",
    "            if not A or A.val != B.val:return False\n",
    "            return recur(A.left,B.left) and recur(A.right,B.right)\n",
    "\n",
    "        if not A or not B: return False\n",
    "        stack = deque([A])\n",
    "        while stack:\n",
    "            l = len(stack)\n",
    "            for i in range(l):\n",
    "                node = stack.popleft()\n",
    "                if node.val == B.val:\n",
    "                    if recur(node, B):\n",
    "                        return True\n",
    "                if node.left: stack.append(node.left)\n",
    "                if node.right: stack.append(node.right)\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A, B):\n",
    "        def recur(A, B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "        \n",
    "        if not A or not B:\n",
    "            return False\n",
    "        return recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def isSub(A,B):\n",
    "            if not B:\n",
    "                return True\n",
    "            elif not A:\n",
    "                return False\n",
    "            elif A.val != B.val:\n",
    "                return False\n",
    "            else:\n",
    "                return isSub(A.left,B.left) and isSub(A.right,B.right)\n",
    "        if not A or not B:\n",
    "            return False\n",
    "        return isSub(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def dfs(A,B):\n",
    "            if B is None:\n",
    "                return True\n",
    "            if A is None:\n",
    "                return False\n",
    "            if A.val!=B.val:\n",
    "                return False\n",
    "            return dfs(A.left,B.left) and dfs(A.right,B.right)\n",
    "        if not B:\n",
    "            return False\n",
    "        if not A:\n",
    "            return False\n",
    "        return  dfs(A,B) or self.isSubStructure(A.left,B) or self.isSubStructure(A.right,B)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        if A is None or B is None:\n",
    "            return False\n",
    "        def recur(A, B):\n",
    "            if not B:\n",
    "                return True\n",
    "            if not A or A.val != B.val:\n",
    "                return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "        \n",
    "        return (recur(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def recur(A, B):\n",
    "            if not B: return True\n",
    "            if not A or A.val != B.val: return False\n",
    "            return recur(A.left, B.left) and recur(A.right, B.right)\n",
    "\n",
    "        return bool(A and B) and (recur(A, B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def helper(A, B):\n",
    "            queue = [(A, B)]\n",
    "            while queue:\n",
    "                nodeA, nodeB = queue.pop(0)\n",
    "                if not nodeA or nodeA.val != nodeB.val:\n",
    "                    return False\n",
    "                if nodeB.left:\n",
    "                    queue.append((nodeA.left, nodeB.left))\n",
    "                if nodeB.right:\n",
    "                    queue.append((nodeA.right, nodeB.right))\n",
    "            return True\n",
    "\n",
    "        if not B: return False\n",
    "        queue = collections.deque([A])\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.val == B.val:\n",
    "                if helper(node, B):\n",
    "                    return True\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        #8:40\n",
    "        if B is None: return False\n",
    "        def isSame(p1,p2):\n",
    "            if p2 is None:\n",
    "                return True\n",
    "            elif p1 is None and p2 is not None:\n",
    "                return False\n",
    "            if p1.val==p2.val:\n",
    "                if isSame(p1.left,p2.left) and isSame(p1.right,p2.right):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            return False\n",
    "        def findRoot(p1,p2):\n",
    "            rt=[]\n",
    "            if p1 is None:\n",
    "                return []\n",
    "            if p1.val == p2.val:\n",
    "                rt.append(p1)\n",
    "            t1= findRoot(p1.left,p2)\n",
    "            t2=findRoot(p1.right,p2)\n",
    "            return rt+t1+t2\n",
    "        plist = findRoot(A,B)\n",
    "        if len(plist) ==0: return False\n",
    "        for p in plist:\n",
    "            print(p.val)\n",
    "            if isSame(p,B):\n",
    "                return True\n",
    "            \n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "        if B is None: return False\n",
    "        def isSame(p1,p2):\n",
    "            if p1 is None and p2 is None:\n",
    "                return True\n",
    "            elif p1 is None or p2 is None:\n",
    "                return False\n",
    "            if p1.val==p2.val:\n",
    "                if isSame(p1.left,p2.left) and isSame(p1.right,p2.right):\n",
    "                    return True\n",
    "                else:\n",
    "                    return False\n",
    "            return False\n",
    "        def findRoot(p1,p2):\n",
    "            if p1 is None:\n",
    "                return None\n",
    "            if p1.val == p2.val:\n",
    "                return p1\n",
    "            else:\n",
    "                t1= findRoot(p1.left,p2)\n",
    "                if t1 is not None : return t1\n",
    "                t2=findRoot(p1.right,p2)\n",
    "                if t2 is not None : return t2\n",
    "                return None\n",
    "        p = findRoot(A,B)\n",
    "        if p is None: return False\n",
    "        return isSame(p,B)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "def my_dfs(node1, node2):\n",
    "    if node1 is None and node2 is None:\n",
    "        return True\n",
    "    if node1 is None:\n",
    "        return False\n",
    "    if node2 is None:\n",
    "        return True\n",
    "    if node1.val != node2.val:\n",
    "        return False\n",
    "    return my_dfs(node1.left, node2.left) and my_dfs(node1.right, node2.right)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        node1 = A \n",
    "        node2 = B \n",
    "        if node1 is None or node2 is None:\n",
    "            return False\n",
    "        queue = [node1]\n",
    "        while len(queue) > 0:\n",
    "            node1 = queue.pop(0)\n",
    "            if node1.left:\n",
    "                queue.append(node1.left)\n",
    "            if node1.right:\n",
    "                queue.append(node1.right)\n",
    "            if node1.val == node2.val:\n",
    "                if my_dfs(node1, node2):\n",
    "                    return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        \"\"\"\n",
    "        判断两颗二叉树是否相同\n",
    "        \"\"\"\n",
    "        def is_same_tree(t1,t2):\n",
    "            # if t1 is None and t2 is None:\n",
    "            if t2 is None:\n",
    "\n",
    "                return True\n",
    "            elif t1 is None or t2 is None:\n",
    "            # elif t1 is None:\n",
    "                return False\n",
    "            elif t1.val != t2.val:\n",
    "                return False\n",
    "            else:\n",
    "                return is_same_tree(t1.left,t2.left) and is_same_tree(t1.right, t2.right)\n",
    "        if A is None or not B:\n",
    "            return False\n",
    "        # if is_same_tree(A,B):\n",
    "        #     return True\n",
    "\n",
    "        return is_same_tree(A,B) or self.isSubStructure(A.left, B) or self.isSubStructure(A.right, B)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        target_tree = B\n",
    "        wether_can = False\n",
    "        list_quene = [A]\n",
    "\n",
    "        def dps(node_se, target_node):\n",
    "            nonlocal wether_can\n",
    "            if not wether_can:\n",
    "                return\n",
    "            if target_node is None:\n",
    "                return\n",
    "            elif node_se is not None and target_node is not None:\n",
    "                if node_se.val == target_node.val:\n",
    "                    dps(node_se.left, target_node.left)\n",
    "                    dps(node_se.right, target_node.right)\n",
    "                else:\n",
    "                    wether_can = False\n",
    "                    return\n",
    "            else:\n",
    "                wether_can = False\n",
    "\n",
    "\n",
    "        def bps(list_quene, target_tree):\n",
    "            nonlocal wether_can\n",
    "            now_list_quene = list_quene.copy()\n",
    "            for tree in now_list_quene:\n",
    "                if tree is not None:\n",
    "                    if tree.val == target_tree.val:\n",
    "                        wether_can = True\n",
    "                        dps(tree, target_tree)\n",
    "                        if wether_can:\n",
    "                            return\n",
    "                if tree.left is not None:\n",
    "                    list_quene.append(tree.left)\n",
    "                if tree.right is not None:\n",
    "                    list_quene.append(tree.right)\n",
    "                list_quene.pop(0)\n",
    "\n",
    "        if target_tree is not None:\n",
    "            while len(list_quene) != 0 and not wether_can:\n",
    "                bps(list_quene, target_tree)\n",
    "\n",
    "        return wether_can\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def isSubStructure(self, A: TreeNode, B: TreeNode) -> bool:\n",
    "        def helper(a,b):\n",
    "            if not b:\n",
    "                return True\n",
    "            if not a or a.val != b.val:\n",
    "                return False\n",
    "            return helper(a.left,b.left) and helper(a.right, b.right)\n",
    "        if not B: return False\n",
    "        que = collections.deque()\n",
    "        que.append(A)\n",
    "        while que:\n",
    "            node = que.popleft()\n",
    "            if node.val == B.val:\n",
    "                if helper(node,B):\n",
    "                    return True\n",
    "            if node.left:que.append(node.left)\n",
    "            if node.right:que.append(node.right)\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
